# 剑指Offer题解 - Day24
# 剑指 Offer 22. 链表中倒数第 k 个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表:1->2->3->4->5, 和k= 2.
返回链表 4->5.
1
2
3
2
3
思路：
本题涉及到链表，因此优先考虑使用双指针解决。
如果直接采取遍历的话，需要遍历两遍。第一遍用来获取链表的长度，第二遍循环链表长度减去k次，就可以获取到倒数第k个节点。
如果采取双指针的思路，那么这里需要声明两个快慢指针。可以先让快指针走k步，然后两个指针一起走，直到快指针的节点为null ，此时慢指针所处的节点就是倒数第k个节点。
两个指针一起走的时候，可以理解为是一个固定宽度为k的滑动窗口，当窗口的右侧跑到链表末尾时，窗口的左侧就是要寻找的节点。
# 双指针(快慢指针)
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let step = k; // 缓存k值，方便让快指针先走k步
let slow = head; // 初始化慢指针
let fast = head; // 初始化快指针
while(step && fast) { // 快指针先走k步
fast = fast.next;
step--;
}
while(fast) { // 快慢指针一起走，直到快指针的节点为null
fast = fast.next;
slow = slow.next;
}
return slow; // 返回慢指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
- 时间复杂度 O(n)。
- 空间复杂度 O(1)。
# 总结
为了防止k越界，这里在第一个while循环中做了不为空的判断处理。第二个while循环使快慢指针一起移动，直到快指针所指节点为null为止。
时间复杂度方面，由于需要遍历整个链表，因此时间复杂度是O(n) ；维护了额外的三个变量，因此空间复杂度是O(1)。